void solve()
{
  int n;
  cin >> n;

  set<int> fac;
  for (int i = 1, d = sqi(n); i <= d; i++) {
    if (n % i == 0) {
      if (i > 1) {
        fac.insert(i);
      }
      if (n / i > 1) {
        fac.insert(n / i);
      }
    }
  }
  
  vi ans;
  ans.pb(*fac.begin());
  fac.erase(fac.begin());
  int ret = 0;
  while (sz(fac)) {
    int find = -1;
    for (auto &v : fac) {
      if (__gcd(v, ans.back()) != 1) {
        find = v;
        break;
      }
    }

    if (find == -1) {
      ret++;
      find = *fac.begin();
    }
    fac.erase(find);
    ans.pb(find);
  }

  ret += __gcd(ans.front(), ans.back()) == 1;
  for (auto &v : ans) {
    cout << v << ' ';
  }
  cout << '\n';
  cout << ret << '\n';
}